package qjc.g_链表;

import com.链表.练习题.ListNode;

public class g10_K个一组翻转链表 {
    /**
     * 创建一个虚拟头节点，方便操作，初始化 pre 指针，指向虚拟头节点，
     * 初始化 end 指针，指向虚拟头节点，遍历链表，每次处理 K 个节点，
     * 移动 end 指针，使其领先 pre 指针 K 个节点，
     * 如果 end 指针到达链表末尾，说明剩余节点不足 K 个，直接退出循环，
     * 保存当前组的起始节点，保存下一组的起始节点，断开当前组与下一组的连接，
     * 翻转当前组，重新连接翻转后的组与下一组，移动 pre 指针到当前组的最后一个节点，
     * 重置 end 指针到 pre 指针的位置
     */
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode s = new ListNode(-1,head);
        ListNode pre = s;
        ListNode end = s;
        while (end.next != null){
            for (int i = 0; i < k && end != null; i++) {
                end = end.next;
            }
            if (end == null){
                break;
            }
            ListNode start = pre.next;
            ListNode next = end.next;
            end.next = null;
            pre.next = reverse(start);
            start.next = next;
            pre = start;
            end = pre;
        }
        return s.next;
    }

    private ListNode reverse(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null){
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
}
